package com.itheima.leetcode.od.b.dynamicprogramming;

/**
 * (C卷,200分)- 两个字符串间的最短路径问题（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 给定两个字符串，分别为字符串 A 与字符串 B。
 * <p>
 * 例如 A字符串为 "ABCABBA"，B字符串为 "CBABAC" 可以得到下图 m * n 的二维数组，定义原点为(0,0)，终点为(m,n)，水平与垂直的每一条边距离为1，映射成坐标系如下图。
 * <p>
 * 从原点 (0,0) 到 (0,A) 为水平边，距离为1，从 (0,A) 到 (A,C) 为垂直边，距离为1；
 * <p>
 * 假设两个字符串同一位置的两个字符相同，则可以作一个斜边，如 (A,C) 到 (B,B) 最短距离为斜边，距离同样为1。
 * <p>
 * 作出所有的斜边如下图，(0,0) 到 (B,B) 的距离为：1 个水平边 + 1 个垂直边 + 1 个斜边 = 3。
 * <p>
 * 根据定义可知，原点到终点的最短距离路径如下图红线标记，最短距离为9：
 * <p>
 * 输入描述
 * <p>
 * 空格分割的两个字符串 A 与字符串 B
 * <p>
 * 字符串不为"空串"
 * 字符格式满足正则规则：[A-Z]
 * 字符串长度 < 10000
 * 输出描述
 * 原点到终点的最短距离
 * <p>
 * 用例
 * <p>
 * 输入	ABC ABC
 * 输出	3
 * 说明	无
 * <p>
 * 输入	ABCABBA CBABAC
 * 输出	9
 * 说明	无
 * <p>
 * 题目解析
 * <p>
 * 本题可以通过动态规划来求解：
 * <p>
 * 我们假设dp[i][j]表示(0,0)到(i,j)的最短距离，那么这个最短距离只可能来自三个方向：
 * <p>
 * dp[i-1][j]，当前点的上方点
 * dp[i][j-1]，当前点的左边点
 * dp[i-1][j-1]，当前点的左上方点
 * 而存在推导式如下：
 * <p>
 * dp[i][j] = min(dp[i-1][j]，dp[i][j-1]，dp[i-1][j-1]) + 1
 * <p>
 * 另外需要注意的是，上面推导式dp[i-1][j-1]参与比较是有前提条件的，即如果(i-1, j-1)点和(i,j)点之间存在斜线相连时，才能将dp[i-1][j-1]带入上面推导式，否则不能带入。
 * <p>
 * 并且上面推导式还可以优化，如果当前点可以向三个方向扩散：
 * <p>
 * 向右
 * 向下
 * 向右下
 * 那么向右和向下是否有必要扩散呢？比如下图
 * <p>
 * 从(1,1)处可以向三个方向扩散，此时可以看出扩散后的三个新位置X,Y,Z，其中Y要比X,Z更靠近右下角点。
 * <p>
 * 那么有没有可能存在一种路径，比如Z点沿着这条路径到达右下角点更快呢？我们改造一下上面图示：
 * <p>
 * 假设存在下面路径，可以让Z点快速到达右下角点，此时我们可以发现，其实Y点也可以凭借该路径以一样的路径长度到达
 * <p>
 * 因此，如果如果存在一条路径可以让Z快速到达右下角点，那么Y一定也可以借用到这条路径，以一样的距离到达右下角点。再给个图示例子：
 * <p>
 * 因此，优化思路是，如果当前点可以向三个方向扩散，那么此时可以只扩散：向右下斜边方向。
 * <p>
 * 即推导式可以变为：
 * <p>
 * 如果（i-1, j-1）和（i,j）之间存在斜线相连，则dp[i][j] = dp[i-1][j-1] + 1
 * 否则：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
 * 本题数量级较大，因此如果构造一个m行n列的dp矩阵，那么会超出内存限制。
 * <p>
 * 优化思路是使用压缩数组，我们可以先看下下面的纯动态规划解法，可以发现
 * <p>
 * 初始化好dp数组的第一行，第一列后，我们通过两个for循环开始完成dp数组其他位置元素的求解，但是本质上还是逐行求解的。
 * <p>
 * 因此，我们完全只需要保留两行：preRow用于记录前一行的dp元素值，curRow用于保存当前行的dp元素值。
 * <p>
 * curRow仅需要根据preRow即可完成所有元素求解。（PS：curRow的第一列元素值取值即为所在行号）
 * <p>
 * 这样我们就避免了dp数组记录一些过期数据。
 */
public class ShortestPathBetweenTwoStrings {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        A = sc.next();
        B = sc.next();

        m = B.length();
        n = A.length();*/

        String[] arr = "ABCABBA CBABAC".split(" ");

        System.out.println(getResult1(arr));
        System.out.println(getResult2(arr));
    }

    /**
     * 二维数组
     *
     * @return
     */
    public static int getResult1(String[] arr) {
        String A = arr[0];
        String B = arr[1];
        int m = B.length();
        int n = A.length();

        // dp[i][j] 记录的是(0,0)到达点(i, j)的最短路径
        int[][] dp = new int[m + 1][n + 1];

        // (0,0)到达矩阵第一行上的各点的最短路径，即为(0,0) -> (0,j) 的直线路径
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // (0,0)到达矩阵第一列上的各点的最短路径，即为(0,0) -> (i,0) 的直线路径
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A.charAt(j - 1) == B.charAt(i - 1)) {
                    // 如果可以走斜线，则选走斜线的点
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 如果不能走斜线，则从当前点的上方点、左方点中选择一个较小值
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[m][n];
    }

    /**
     * 一维数组（压缩数组）
     *
     * @param arr
     * @return
     */
    public static int getResult2(String[] arr) {
        String A = arr[0];
        String B = arr[1];
        int m = B.length();
        int n = A.length();

        // 初始时preRow记录第一行上各点到(0,0)点的最短距离，即为(0,0) -> (0,j) 的直线路径
        int[] preRow = new int[n + 1];
        for (int j = 0; j <= n; j++) {
            preRow[j] = j;
        }

        // 初始时curRow记录第二行上各点到(0,0)点的最短距离
        int[] curRow = new int[n + 1];

        for (int i = 1; i <= m; i++) {
            // curRow[0]是指 (i, 0)点 到 (0,0)点 的最短距离，即为(0,0) -> (i, 0) 的直线路径
            curRow[0] = i;

            for (int j = 1; j <= n; j++) {
                if (A.charAt(j - 1) == B.charAt(i - 1)) {
                    // 如果可以走斜线，则选走斜线的点
                    curRow[j] = preRow[j - 1] + 1;
                } else {
                    // 如果不能走斜线，则从当前点的上方点、左方点中选择一个较小值
                    curRow[j] = Math.min(preRow[j], curRow[j - 1]) + 1;
                }
            }

            // 压缩
            System.arraycopy(curRow, 0, preRow, 0, n + 1);
        }

        return curRow[n];
    }
}